package com.xingfly.suan;
import java.util.*;

import com.xingfly.model.dto.Seat;
import com.xingfly.model.dto.User;
import com.xingfly.suan.Pos;
/**
 * 	整仓分配
 * @author 纸短情长
 *
 */
public class FlightArithmetic {
	   static int max = 0;
	    //记录团体查找连坐的迭代次数
	    static int iterations = 0;

	    static int last = 0;

	    public static Map<String, Object> Allot(List<User> lus, List<Seat> seas, int serial) {
	        //如果待分配人数大于1则执行多人分配算法
	        //否则将按照单人，匹配个人需求
	        if (lus.size() > 1) {
	            //记录团体查找连坐的迭代次数
	            iterations = 0;
	            return AllotMore(lus, seas, serial);
	        } else {
	            return AllotOne(lus, seas, serial);
	        }
	    }

	    private static Map<String, Object> AllotMore(List<User> lus, List<Seat> seas, int serial) {

	        int sum = lus.size();//待分配人数
	        boolean flag = true;//记录左右分配人数是否不足
	        Stack<Pos> Overall = new Stack<>();
	        int[][] mode = Init(seas);
	        List<Seat> Tseat = new ArrayList<>();
	        long startTime = System.currentTimeMillis();
	        //满意度阶梯人数，每个梯度的人数
	        List<Integer> ladder = new ArrayList<>();
	        //如果找到连坐不满足总人数，则将该连坐分配到部分团体用户
	        //然后剩下的人再次分配连坐
	        while (sum > 0) {
	            max = 0;
	            last = 0;
	            //左半舱搜索
	            flag = GetSet(mode, Overall, sum, 0, 3);
	            //如果在左半舱找到满足位置，将不进行右半仓搜索
	            if (!flag) {
	                //右半舱搜索
	                GetSet(mode, Overall, sum, 3, 6);
	            }
	            ladder.add(Overall.size());
	            sum -= Overall.size();
	            List<Pos> poss = new ArrayList<>(Overall);
	            for (Pos s : poss) {
	                mode[s.y][s.x] = 1;
	                for (Seat se : seas) {
	                    if (se.getSeid() == (s.y * 6 + s.x + 1)) {
	                        Tseat.add(se);
	                    }
	                }
	            }
	            Overall.clear();
	        }
	        //如找到连坐，或找到最大连坐，则按个人偏好将每个人分配到这些座位
	        Map map = AllotOne(lus, Tseat, serial);
	        long endTime = System.currentTimeMillis();    //获取结束时间
	        long sfhs = endTime - startTime;
	        //算法耗时
	        map.put("sfhs", sfhs);
	        //迭代次数
	        map.put("ddcs", iterations + (int) map.get("ddcs"));
	        List<Temp> temp = (List<Temp>) map.get("tempData");
	        float satisfa = (float) (100 * 1.0) / temp.size();
	        //循环更新满意度
	        int te = 0;
	        int maptempmax = 0;
	        for (Integer t : ladder) {
	            for (int i = te; i < t + te; i++) {
	                if (maptempmax < t)
	                    maptempmax = t;
	                temp.get(i).setSatis(t * satisfa);
	            }
	            te = te + t;
	        }
	        map.put("bcfpmyd", (float) maptempmax * satisfa);
	        map.put("tempData", temp);
	        return map;
	    }

	    //团体分配先分配连坐，在连坐的基础上按单人偏好分配
	    private static boolean GetSet(int[][] mode, Stack<Pos> Overall, int sum, int start, int end) {
	        //先左半舱查找，如果未找到满足连坐，则需要继续右半仓查找，否则不需要
	        //System.out.println(sum);
	        boolean flag = false;
	        int cut = 0;
	        int cur = 0;
	        int cui, cuj;
	        //存放临时座位信息
	        Stack<Pos> sck = new Stack<>();
	        for (int i = 33; i >= 0; i--) {
	            for (int j = 0; j < 3; j++) {
	                iterations++;
	                //如果在找到连坐，则退出查找
	                if (cur >= sum) {
	                    break;
	                }
	                cui = i;
	                //根据参数来实现左或右半仓搜索
	                cuj = i % 2 == 1 ? j + start : end - 1 - j;
	                //判断座位是否有人
	                if (mode[cui][cuj] != 1) {
	                    cut++;
	                    mode[cui][cuj] = 2;
	                    Pos p = new Pos();
	                    p.y = cui;
	                    p.x = cuj;
	                    sck.push(p);
	                    //System.out.println("扫描座位");
	                    if (cut > 1) {
	                        if (Getpos(mode, cui, cuj, start, end)) {
	                            cur = cut;
	                        } else {
	                            if (cur > max) {
	                                Overall.clear();
	                                if (!sck.isEmpty()) {
	                                    Pos po = sck.pop();
	                                    mode[po.y][po.x] = 0;
	                                }
	                                while (!sck.isEmpty()) {
	                                    Pos ps = sck.pop();
	                                    mode[ps.y][ps.x] = 0;
	                                    Overall.push(ps);
	                                }
	                                max = cut - 1;
	                            }
	                            cut = 0;
	                            sck.clear();
	                            j--;
	                            continue;
	                        }
	                    } else {
	                        cur = cut;
	                    }
	                }
	            }
	            if (cur >= sum) {
	                flag = true;
	                break;
	            }
	        }

	        if (cur > max)
	            max = cur;

	        //当查找人数不满足连坐时，获取做大连坐数量
	        if (max < sum) {
	            if (max > last) {
	                if (sck.size() > Overall.size()) {
	                    Overall.clear();
	                }
	                while (!sck.isEmpty()) {
	                    Pos p = sck.pop();
	                    mode[p.y][p.x] = 0;
	                    Overall.push(p);
	                }
	            }
	        } else {
	            //当查找人数不满足连坐时，获取做大连坐数量
	            Overall.clear();
	            while (!sck.isEmpty()) {
	                Pos p = sck.pop();
	                Overall.push(p);
	            }
	        }
	        last = max;
	        return flag;
	    }

	    //遍历机舱越界检查
	    private static boolean Getpos(int[][] arr, int y, int x, int start, int end) {
	        boolean flag = false;
	        if (x - 1 >= start) {
	            if (arr[y][x - 1] == 2) {
	                flag = true;
	            }
	        }
	        if (x + 1 < end) {
	            if (arr[y][x + 1] == 2) {
	                flag = true;
	            }
	        }
	        if (y - 1 >= 0) {
	            if (arr[y - 1][x] == 2) {
	                flag = true;
	            }
	        }
	        if (y + 1 < 34) {
	            if (arr[y + 1][x] == 2) {
	                flag = true;
	            }
	        }
	        return flag;
	    }

	    //将座位列表转换成二维数组方便多人分配查找
	    private static int[][] Init(List<Seat> seas) {
	        int[][] arr = new int[204 / 6][6];
	        for (int i = 0; i < arr.length; i++) {
	            for (int j = 0; j < arr[0].length; j++) {
	                arr[i][j] = 1;
	            }
	        }
	        for (Seat s : seas) {
	            int x = s.getSeid() % 6 == 0 ? 5 : s.getSeid() % 6 - 1;
	            int y = s.getSeid() % 6 == 0 ? s.getSeid() / 6 - 1 : s.getSeid() / 6;

	            arr[y][x] = 0;
	        }
	        return arr;
	    }


	    //单人按个人偏好分配
	    private static Map<String, Object> AllotOne(List<User> lus, List<Seat> seas, int serial) {
	        Map<String, Object> map = new HashMap<>();
	        List<Temp> tempData = new LinkedList<>();
	        int count = 0, index, max = 0, reminx = 0;
	        float bcfpmyd = 0;
	        Seat sea = null;
	        String SeatType = null;
	        String utstr = null;
	        String[] ut = null;

	        long startTime = System.currentTimeMillis();
	        //用户集合
	        int ddcs = 0;
	        int zwrem;
	        for (User utmp : lus) {
	            index = -1;
	            zwrem = 0;
	            reminx = 0;
	            utstr = utmp.getPrefer();
	            ut = utstr.split(",");
	            //座位集合
	            for (Seat stmp : seas) {
	                count = 0;
	                SeatType = stmp.getSeatType();
	                for (int i = 0; i < ut.length; i++) {
	                    if (SeatType.contains(ut[i]))
	                        count++;
	                }
	                //如果上述座位满足用户条件，且条件长度一致，且满足用户的条件个数和座位条件个数一致
	                if (utstr.length() == SeatType.length() && count == SeatType.split(",").length) {
	                    sea = stmp;
	                    reminx = zwrem;
	                    max = count;
	                    break;
	                }

	                if (count > index) {
	                    sea = stmp;
	                    max = count;
	                    reminx = zwrem;
	                    index = count;
	                }
	                zwrem++;
	                ddcs++;
	            }
	            Temp temp = new Temp(utmp.getUid(), sea.getSeid(), serial, (float) (max / (1.0 * ut.length)) * 100, utmp.getPrefer());
	            tempData.add(temp);
	            seas.remove(reminx);
	        }

	        long endTime = System.currentTimeMillis();    //获取结束时间
	        long sfhs = endTime - startTime;
	        //计算本次满意度
	        for (Temp s : tempData) {
	            bcfpmyd += s.getSatis();
	        }
	        bcfpmyd /= tempData.size();

	        map.put("sfhs", sfhs);
	        map.put("ddcs", ddcs);
	        map.put("bcfpmyd", bcfpmyd);
	        map.put("tempData", tempData);
	        return map;
	    }
}
